#include <iostream>
#include <queue>
#include <memory>

using namespace std;

typedef struct TreeNode {
    int data;
    TreeNode* leftNode;
    TreeNode* rightNode;

    TreeNode(int data): data(data),leftNode(nullptr),rightNode(nullptr){}
}TreeNode;

class BinaryTree {
private:
    TreeNode* root;
public:
    BinaryTree():root(nullptr) {}

    BinaryTree(int val){
        root = new TreeNode(val);
    }

    ~BinaryTree(){
        delete(root);
    }

    TreeNode* getRoot() const {
        return root;
    }

    bool isEmpty() const {
        return root == nullptr;
    }

    void insert(int val){
        TreeNode* newNode = new TreeNode(val);
        if(isEmpty()){
            root = newNode;
            return;
        }

        queue<TreeNode*> queue;
        queue.push(root);

        while(!queue.empty()){
            TreeNode* current = queue.front();
            queue.pop();

            if(current -> leftNode == nullptr){
                current -> leftNode = newNode;
                return;
            }else if(current -> rightNode == nullptr){
                current -> rightNode = newNode;
                return;     
            }else{
                queue.push(current->leftNode);
                queue.push(current->rightNode);
            }
        }
    }

    void preorderTraversal(TreeNode* node)const{
        if (node == nullptr) return;

        cout << node->data << " ";
        preorderTraversal(node->leftNode);
        preorderTraversal(node->rightNode);
    }


    void inorderTraversal(TreeNode* node)const{
        if(node == nullptr) return;

        inorderTraversal(node->leftNode);
        cout << node->data << " ";
        inorderTraversal(node->rightNode);
    }

    void postordertraversal(TreeNode* node)const{
        if(node == nullptr) return;
        postordertraversal(node->leftNode);
        postordertraversal(node->rightNode);
        cout << node->data<<" ";
    }

    void levelOrderTraversal(TreeNode* node)const{
        if(node == nullptr) return;

        queue<TreeNode*> queue;
        queue.push(root);
        
        while(!queue.empty()){
            TreeNode* current = queue.front();
            queue.pop();
            cout << current->data << " ";
            if(current->leftNode != nullptr){
                queue.push(current->leftNode);
            }

            if(current->rightNode != nullptr){
                queue.push(current->rightNode);
            }
        }
    }

    int height(TreeNode* node) const {
        if(node == nullptr) return 0;

        int leftHeight = height(node->leftNode);
        int rightHeight = height(node->rightNode);
        return max(leftHeight,rightHeight)+1;
    }
    
    int countNode(TreeNode* node)const{
        if(node == nullptr) return  0;

        return 1 + countNode(node->leftNode)+countNode(node->rightNode);
    }

    bool search(TreeNode* node,int value) const {
        if(node == nullptr) return false;
        if(node->data == value) return true;

        return search(node->leftNode,value)||search(node->rightNode,value);
    }

private:
    void clear(TreeNode* node){
        if(node == nullptr) return;
        clear(node->leftNode);
        clear(node->rightNode);
        delete node;
    }
};


int main(){
    BinaryTree b(10);
    b.insert(20);
    b.insert(40);
    b.insert(50);
    b.insert(100);

    b.inorderTraversal(b.getRoot());
    cout << "\n";
    b.preorderTraversal(b.getRoot());
    cout << "\n";
    b.postordertraversal(b.getRoot());
    cout << "\n";
}